package com.suanfa.collect;

/**
 * 二分法查找目标元素在数组中的起始截止位置
 */
public class BinSearch {

    public static void main1(String[] args) {
        int[] arr = new int[]{5,7,7,8,8,10};
        //System.out.println(getResult(arr, 8));
        int[] arr1 = new int[]{2,2};
        System.out.println(searchRange(arr1, 8));
    }


    public static int[] getResult(int[] arr, int target){

        int start = binarySearch(arr, target);
        int end = binarySearch(arr,target+1);
        if(arr.length==0|| start == arr.length|| arr[start] != target){
            return new int[]{-1,-1};
        }
        return new int[]{start, end-1};

    }

    public static int binarySearch(int[] arr, int target){
            int s = 0, e = arr.length;
            while(s < e){
                int min = (e+s) >>1;
                if(arr[min] >= target){
                    e = min;
                }else{
                    s = min+1;
                }
            }
            return s;

    }



    //先找>=target的第一个
    //再找>target的第一个
    //我真是这辈子都不想看见这题
    public static int[] searchRange(int[] nums, int target) {
        int l=search(nums,target);
        int r=search(nums,target+1);
            if(l==nums.length||nums[l]!=target)
            return new int[]{-1,-1};
        return new int[]{l,r-1};
    }
    //找>=target的第一个
    public static int search(int[] nums,int target){
        int l=0,r=nums.length;
        while(l<r){
            int mid=(r+l)>>1;
            if(nums[mid]>=target)
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }

}
